#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node
{
    int key;
    void *value;
    struct Node *next;
} Node;

typedef struct Map
{
    Node **buckets;
    int size;
} Map;

// 定义迭代器结构体
typedef struct Iterator
{
    Map *map;
    int bucket_idx;
    Node *node;
} Iterator;

// 创建一个新的节点
Node *createNode(int key, void *value)
{
    Node *node = (Node *)malloc(sizeof(Node));
    if (node == NULL)
    {
        perror("Error: unable to allocate memory for new node.");
        exit(EXIT_FAILURE);
    }
    node->key = key;
    node->value = value;
    node->next = NULL;
    return node;
}

// 删除一个节点
void deleteNode(Node *node)
{
    free(node);
}

// 计算哈希值
int hash(int key, int size)
{
    int hash = 0;
    hash = 31 * hash + key;
    return abs(hash % size);
}

// 创建一个新的 Map
Map *CreateMap(int size)
{
    Map *map = (Map *)malloc(sizeof(Map));
    if (map == NULL)
    {
        perror("Error: unable to allocate memory for new map.");
        exit(EXIT_FAILURE);
    }
    map->size = size;
    map->buckets = (Node **)calloc(size, sizeof(Node *));
    if (map->buckets == NULL)
    {
        perror("Error: unable to allocate memory for buckets.");
        exit(EXIT_FAILURE);
    }
    return map;
}

// 删除一个 Map
void DeleteMap(Map *map)
{
    int i = 0;
    for (; i < map->size; ++i)
    {
        Node *node = map->buckets[i];
        while (node != NULL)
        {
            Node *tmp = node;
            node = node->next;
            deleteNode(tmp);
        }
    }
    free(map->buckets);
    free(map);
}

// 添加键值对
void Put(Map *map, int key, void *value)
{
    int idx = hash(key, map->size);
    Node *node = map->buckets[idx];
    while (node != NULL)
    {
        if (node->key == key)
        {
            node->value = value;
            return;
        }
        node = node->next;
    }
    node = createNode(key, value);
    node->next = map->buckets[idx];
    map->buckets[idx] = node;
}

// 获取键对应的值，如果不存在则返回 NULL
void *Get(Map *map, int key)
{
    int idx = hash(key, map->size);
    Node *node = map->buckets[idx];
    while (node != NULL)
    {
        if (node->key == key)
            return node->value;
        node = node->next;
    }
    return NULL;
}

int subarraySum(int *nums, int numsSize, int k)
{
    int ret = 0;
    int i, *curValuePtr = malloc(sizeof(int));
    int preCount = 0;
    Map *_map = CreateMap(4096);
    Node *node = NULL;
    *curValuePtr = 1;
    Put(_map, 0, curValuePtr);
    for (i = 0; i < numsSize; i++)
    {
        preCount += nums[i];
        curValuePtr = Get(_map, preCount - k);
        if (curValuePtr != NULL)
        {
            ret += *curValuePtr;
        }

        curValuePtr = Get(_map, preCount);
        if (curValuePtr != NULL)
        {
            (*curValuePtr)++;
        }
        else
        {
            curValuePtr = malloc(sizeof(int));
            *curValuePtr = 1;
            Put(_map, preCount, curValuePtr);
        }
    }
    return ret;
}

int main()
{
    int nums[] = {-1, -1, 1};
    printf("%d\n", subarraySum(nums, sizeof(nums) / sizeof(nums[0]), 0));
    return 0;
}